package __回溯算法

/*
https://leetcode.cn/problems/sudoku-solver/

37. 解数独
编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：
输入：board = [
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]

输出：[
["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]
]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
*/
func solveSudoku(board [][]byte) {

	var dfs func(board [][]byte) bool
	dfs = func(board [][]byte) bool { //定义递归函数
		for i := 0; i < 9; i++ { //遍历每9*9每个格子
			for j := 0; j < 9; j++ {
				if board[i][j] != '.' { //判断此位置是否适合填数字
					continue
				}
				for k := '1'; k <= '9'; k++ { //1-9都尝试填一次
					if isvalid(i, j, byte(k), board) == true { //如果满足要求就填
						board[i][j] = byte(k)
						if dfs(board) == true { //如果当前数字的填法, 满足整个9*9数独要求, 返回true
							return true
						}
						board[i][j] = '.' //走到这里, 说明这种填法并不符合规则, 需要进行还原
					}
				}

				return false //1-9的数字都尝试了, 都没返回true, 说明没有符合规则的数字, 返回false
			}
		}

		return true //这里是为了通过编译, 走不到这里, 符合/不符合的情况, 都在双层遍历中处理了
	}
	dfs(board) //调用递归函数
}

// 判断填入数字是否满足要求
// isvalid
//
//	@Description:
//	@param row		当前行数
//	@param col 		当前列数
//	@param k 		填写的数字
//	@param board 	当前棋盘
//	@return bool 	是否符合数组棋盘规则
func isvalid(row, col int, k byte, board [][]byte) bool {
	for i := 0; i < 9; i++ { //行中不能重复
		if board[row][i] == k {
			return false
		}
	}
	for i := 0; i < 9; i++ { //列中不能重复
		if board[i][col] == k {
			return false
		}
	}

	//同一九宫格不能见重复
	startRow := (row / 3) * 3                // 行除3,求出在第几大行九宫格, 乘以3到该大行的最上层
	startCol := (col / 3) * 3                // 列除3,求出在第几大列九宫格, 乘以3到该大列的最左列
	for i := startRow; i < startRow+3; i++ { //
		for j := startCol; j < startCol+3; j++ {
			if board[i][j] == k {
				return false
			}
		}
	}
	return true
}
